home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / cpp_libs / cool / ge_cool.lha / GE_COOL2.1 / src / Hash_Table / Hash_Table.h < prev    next >
C/C++ Source or Header  |  1992-06-29  |  11KB  |  215 lines
  1. //
  2. // Copyright (C) 1991 Texas Instruments Incorporated.
  3. //
  4. // Permission is granted to any individual or institution to use, copy, modify,
  5. // and distribute this software, provided that this complete copyright and
  6. // permission notice is maintained, intact, in all copies and supporting
  7. // documentation.
  8. //
  9. // Texas Instruments Incorporated provides this software "as is" without
  10. // express or implied warranty.
  11. //
  12. // Created: MBN 05/16/89 -- Initial design and implementation
  13. // Updated: MBN 06/01/89 -- Implemented the notion of current position.
  14. // Updated: MBN 06/06/89 -- Separated and derived Hash_Table from Base_Hash
  15. //                          to reduce replication of common code.
  16. // Updated: LGO 06/20/89 -- Use correct default hash and compare for char* keys
  17. // Updated: LGO 07/03/89 -- Fix resize bug in the put method
  18. // Updated: MBN 08/19/89 -- Changed template usage
  19. // Updated: MBN 09/20/89 -- Added conditional exception handling
  20. // Updated: MBN 09/26/89 -- Added method to return key at current position
  21. // Updated: LGO 10/02/89 -- Substituted Tkey and Tval for T1 and T2
  22. // Updated: MBN 10/07/89 -- Changed get() method to match Association + Symbol
  23. // Updated: MBN 10/11/89 -- Fixed operator==() for tables with different bucket
  24. //                          count but same elements -- tables grew separately
  25. // Updated: MBN 10/12/89 -- Changed "current_position" to "curpos", added
  26. //                          current_position() method for Iterator<Type>, and
  27. //                          converted state from bit set to bit set/get macros
  28. // Updated: LGO 10/16/89 -- Re-write operator<< to be const
  29. // Updated: MBN 10/19/89 -- Made compare_keys and compare_values_s slots static
  30. //                          and added optional argument to set_compare methods
  31. // Updated: MBN 12/15/89 -- Fixed no-dereferenced pointer-to-function in find()
  32. // Updated: LGO 02/07/90 -- Change resize to not use a tempoorary for key and
  33. //                          value.  Avoids extra constructor and destructor
  34. //                          calls.
  35. // Updated: MBN 02/23/90 -- Changed size arguments from long to unsigned long
  36. // Updated: MJF 06/30/90 -- Added base class name to constructor initializer
  37. // Updated: VDN 02/21/92 -- New lite version
  38. //
  39. // The  Hash_Table<Tkey,Tval> class is  publicly  derived from  the  Hash_Table
  40. // class and implements hash tables  of user-specified types  for both the  key
  41. // and the  value.   This is accompilshed  by    using  the parameterized  type
  42. // capability  of C++.   The Hash Table class is  dynamic in nature.  It's size
  43. // (ie.  the number of buckets in the table) is always some prime number.  Each
  44. // bucket holds 8 items.  No wholes are  left in a bucket;  if a key/value pair
  45. // is removed   from the middle of  a  bucket, following  entries are moved up.
  46. // When a  hash  on  a key ends up   in a bucket that  is  full, the  table  is
  47. // enlarged.  The Hash_Table<Tkey,Tval> class  is parameterized over two types.
  48. // The first type Tkey specifies the type of the key,  and the second type Tval
  49. // specifies the type of the value.
  50. //
  51. // The private  data section of  a Hash  Table  has a  slot that points  to the
  52. // physical memory allocated for some prime number of buckets each of which has
  53. // memory allocated for 8 items.  The number of buckets  currently in the table
  54. // is accessed by an index into a global table of selected prime numbers.  This
  55. // global table eliminates the somewhat  expensive runtime computation of prime
  56. // numbers.  The table consists of  prime numbers where  the difference between
  57. // any two successive entries gets progressively larger as you move through the
  58. // table.  The specified range of primes  results in an arbitrary limitation of
  59. // 2^22 entries in a single hash table.
  60. //
  61. // When a hash on a key ends up in a bucket that is full, the table is enlarged
  62. // to the next prime number of buckets or to the prime number  that is at least
  63. // large enough  to  accommodate a user-specified  growth ratio. The entries in
  64. // the  buckets are  then rehashed  into   the new  table.   Selection  of   an
  65. // appropriate   hash function is crucial  to  uniform distribution through the
  66. // table. The result of the hash function is  then divided by the  prime number
  67. // of buckets to accomplish this. A user-supplied  function should do something
  68. // similar.
  69. //
  70. // Other items in the private data section (inherited from Base Hash) include a
  71. // pointer to a byte vector (that is, unsigned char) that  maintains a count of
  72. // the number of entries in each bucket, a growth ratio that can be used to set
  73. // a growth rate percentage when necessary,  an entry count,  an index into the
  74. // prime number table that indicates the number of  buckets in the table, and a
  75. // current position  that maintains the bucket number and index into the bucket
  76. // of the last hash operation.
  77. //
  78. // Three other slots contain a pointer to a key  compare function, a pointer to
  79. // a value compare  function, and a pointer to  a  hash function, respectively.
  80. // The compare functions are  used  in equality  operations on key/value items.
  81. // The default compare function is the  built-in == operator.  The default hash
  82. // function  is either a  simple 32 bit  value if sizeof(Tkey)   is 4,  that is
  83. // shifted left three   bits  with the result  modulo  the  number   of buckets
  84. // determining the  hash. This is  ideal when Tkey is a  pointer to  a key.  If
  85. // sizeof(Tkey) is greater than 4, then the 32 bit value used  is the result of
  86. // exclusive-oring successive 32-bit values  for the  length of Tkey,  and then
  87. // applying the same bit shift and modulo operation as before.
  88. //
  89. // Three different constructors are provided.   The first constructor  takes no
  90. // arguments and  creates a  hash table with  three buckets that  can contain a
  91. // total of 24 items.   The second constructor  accepts an integer argument and
  92. // creates a hash table of some prime number of buckets that  can accomodate at
  93. // least the specified number of items.  Finally, the third constructor takes a
  94. // single argument consisting of a reference to a Hash Table and duplicates its
  95. // size and contents.
  96. //
  97. // The  Hash Table  class implements the notion  of a current position. This is
  98. // useful for  iterating through    the  table of  hashed values.   The current
  99. // position is maintained in a a long that is accessed via several preprocessor
  100. // macros to select bits. The first bit field is of length 24 and maintains the
  101. // bucket  (prime) number last  used.  The second bit field is  of length 8 and
  102. // maintains the index of the last item in a  bucket. Methods to reset, move to
  103. // the next and previous, find, and get  the value at  the current position are
  104. // provided.
  105. //
  106. // Methods are provided to put a value based on some  key into the table, get a
  107. // value based on some key from the  table,  remove  a value  based on some key
  108. // from the table, and to clear all values from the table entirely. The output,
  109. // assignment, and equality operators are overloaded for hash  tables. Finally,
  110. // two functions to  set the hash  and compare functions  for an instance of  a
  111. // hash table, accessor methods to get the bucket and total entry count,  and a
  112. // method to set the growth ratio are also available.
  113.  
  114. #ifndef HASH_TABLEH                // If no Hash Table class,
  115. #define HASH_TABLEH                // define it
  116.  
  117. #ifndef BASE_HASH_TABLEH            // If no Base Hash class,
  118. #include <cool/Base_Hash.h>            // define it
  119. #endif    
  120.  
  121. template <class Tkey, class Tval> CoolHash_Table {
  122.   struct CoolHash_Table<Tkey,Tval>_pair {        // Structure for hash/value
  123.     Tkey key;
  124.     Tval value;
  125.   };
  126.  
  127.   struct CoolHash_Table<Tkey,Tval>_bucket {        // Structure for bucket
  128.     struct CoolHash_Table<Tkey,Tval>_pair data[BUCKET_SIZE];
  129.   };
  130.  
  131.   typedef Boolean
  132.     (*CoolHash_Table<Tkey,Tval>_Key_Compare) (const Tkey&, const Tkey&);
  133.   typedef Boolean
  134.     (*CoolHash_Table<Tkey,Tval>_Value_Compare) (const Tval&, const Tval&);
  135.   typedef unsigned long (*CoolHash_Table<Tkey,Tval>_Hash) (const Tkey&);
  136. }
  137.  
  138.  
  139. template <class Tkey, class Tval>
  140. class CoolHash_Table<Tkey,Tval> : public CoolHash_Table {
  141. public:
  142.   CoolHash_Table<Tkey,Tval> ();            // Hash table of default size
  143.   CoolHash_Table<Tkey,Tval> (unsigned long);    // Hash table for at least size
  144.   CoolHash_Table<Tkey,Tval> (const CoolHash_Table<Tkey,Tval>&); // Copy constructor
  145.   ~CoolHash_Table<Tkey,Tval>();            // Destructor
  146.  
  147.   Boolean put (const Tkey&, const Tval&);       // Hash key/value
  148.   Boolean get (const Tkey&, Tval&);        // Get associated value for key
  149.   Boolean get_key (const Tval&, Tkey&);        // Get associated key for value
  150.   Boolean remove (const Tkey&);            // Remove key/value from table
  151.   void resize (long);                // Resize for at least count
  152.   
  153.   Boolean find (const Tkey&);            // Set current position
  154.   const Tkey& key ();                // Get key at current position
  155.   Boolean remove ();                // Remove key/value at curpos
  156.   const Tval& value ();                // value at current position
  157.  
  158.   CoolHash_Table<Tkey,Tval>& operator= (const CoolHash_Table<Tkey,Tval>&);
  159.   Boolean operator== (const CoolHash_Table<Tkey,Tval>&); // is equal
  160.   inline Boolean operator!= (const CoolHash_Table<Tkey,Tval>&); // is not eq
  161.  
  162.   inline void set_hash (CoolHash_Table<Tkey,Tval>_Hash); // Set hash function
  163.   void set_key_compare (CoolHash_Table<Tkey,Tval>_Key_Compare = NULL); 
  164.   void set_value_compare (CoolHash_Table<Tkey,Tval>_Value_Compare = NULL);
  165.  
  166.   friend ostream& operator<< (ostream&, const CoolHash_Table<Tkey,Tval>&);
  167.   inline friend ostream& operator<< (ostream&, const CoolHash_Table<Tkey,Tval>*);
  168.  
  169. protected:
  170.   CoolHash_Table<Tkey,Tval>_bucket* table;    // Pointer to key/value buckets
  171.   CoolHash_Table<Tkey,Tval>_Hash h_function;    // Pointer to hash function
  172.   static CoolHash_Table<Tkey,Tval>_Key_Compare compare_keys_s; // Key compare
  173.   static CoolHash_Table<Tkey,Tval>_Value_Compare compare_values_s; // Value compare
  174.   friend Boolean CoolHash_Table<Tkey,Tval>_keys_equal (const Tkey&, const Tkey&);
  175.   friend Boolean CoolHash_Table<Tkey,Tval>_values_equal (const Tval&, const Tval&);
  176.   friend unsigned long CoolHash_Table<Tkey,Tval>_default_hash (const Tkey& key);
  177. };
  178.  
  179. // operator<< -- Overload the output operator to provide a crude print
  180. //               capability for hash table objects
  181. // Input:        ostream reference, hash table pointer
  182. // Output:       None
  183.  
  184. template <class Tkey, class Tval> CoolHash_Table {
  185. inline ostream& operator<< (ostream& os, const CoolHash_Table<Tkey,Tval>* h) {
  186.   return operator<< (os, *h);
  187. }
  188. }
  189.  
  190.  
  191.  
  192.  
  193. // operator!= -- Determine if two hash tables are unequal
  194. // Input:        this*, reference to second hash table
  195. // Output:       TRUE/FALSE
  196.  
  197. template <class Tkey, class Tval> 
  198. inline Boolean CoolHash_Table<Tkey,Tval>::operator!= (const CoolHash_Table<Tkey,Tval>& t) {
  199.   return (!operator== (t));
  200. }
  201.  
  202.  
  203.  
  204.  
  205. // Set_hash -- Set the hash function for this instance
  206. // Input:      Pointer to hash function
  207. // Output:     None
  208.  
  209. template <class Tkey, class Tval> 
  210. inline void CoolHash_Table<Tkey,Tval>::set_hash (CoolHash_Table<Tkey,Tval>_Hash h) {
  211.   this->h_function = h;
  212. }
  213.  
  214. #endif                // End #ifdef of HASH_TABLEH
  215.